package com.tgy.algorithm.base._贪心;

import java.util.Comparator;
import java.util.PriorityQueue;

public class _金条分割 {

    public static int goldSplit(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        // 小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for (int i = 0; i < nums.length; i++) {
            minHeap.add(nums[i]);
        }

        int result = 0;
        while (minHeap.size() > 1) {
            int min = minHeap.poll();
            int max = minHeap.poll();
            int sum = min + max;
            result += sum;
            minHeap.add(sum);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{10,20,30};
        int total = goldSplit(nums);
        System.out.println(total);
    }
}
